{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Removing Minimum and Maximum From Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDeletions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从数组中移除最大值和最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>nums</code> ，数组由若干 <strong>互不相同</strong> 的整数组成。</p>\n",
    "\n",
    "<p><code>nums</code> 中有一个值最小的元素和一个值最大的元素。分别称为 <strong>最小值</strong> 和 <strong>最大值</strong> 。你的目标是从数组中移除这两个元素。</p>\n",
    "\n",
    "<p>一次 <strong>删除</strong> 操作定义为从数组的 <strong>前面</strong> 移除一个元素或从数组的 <strong>后面</strong> 移除一个元素。</p>\n",
    "\n",
    "<p>返回将数组中最小值和最大值 <strong>都</strong> 移除需要的最小删除次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,<em><strong>10</strong></em>,7,5,4,<em><strong>1</strong></em>,8,6]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "数组中的最小元素是 nums[5] ，值为 1 。\n",
    "数组中的最大元素是 nums[1] ，值为 10 。\n",
    "将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。\n",
    "结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,<em><strong>-4</strong></em>,<em><strong>19</strong></em>,1,8,-2,-3,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "数组中的最小元素是 nums[1] ，值为 -4 。\n",
    "数组中的最大元素是 nums[2] ，值为 19 。\n",
    "将最大值和最小值都移除需要从数组前面移除 3 个元素。\n",
    "结果是 3 ，这是所有可能情况中的最小删除次数。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [<em><strong>101</strong></em>]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。\n",
    "移除它只需要 1 次删除操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums</code> 中的整数 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [removing-minimum-and-maximum-from-array](https://leetcode.cn/problems/removing-minimum-and-maximum-from-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [removing-minimum-and-maximum-from-array](https://leetcode.cn/problems/removing-minimum-and-maximum-from-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,10,7,5,4,1,8,6]', '[0,-4,19,1,8,-2,-3,5]', '[101]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        i = nums.index(min(nums))\n",
    "        a = nums.index(max(nums))\n",
    "        if i<a:\n",
    "            t = min(i+1,len(nums)-a)+a-i\n",
    "            t1 = min(t,i+1+len(nums)-a)\n",
    "            return t1\n",
    "        t = min(a+1,len(nums)-i)+i-a\n",
    "        t1 = min(t,a+1+len(nums)-i)\n",
    "        return t1'''\n",
    "class Solution(object):\n",
    "    def minimumDeletions(self, nums):\n",
    "        n, i, j = len(nums), nums.index(min(nums)), nums.index(max(nums))\n",
    "        if i > j: i, j = j, i\n",
    "        return min(i + 1 + n - j, j + 1, n - i)         \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        max_i = min_i = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > nums[max_i]:\n",
    "                max_i = i\n",
    "            elif x < nums[min_i]:\n",
    "                min_i = i\n",
    "        \n",
    "        if max_i > min_i:\n",
    "            left, right = min_i, max_i\n",
    "        else:\n",
    "            left, right = max_i, min_i\n",
    "        return min(right + 1, n - left, left + 1 + n - right)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        # 分为3种\n",
    "        # 1. 左 2. 右 3. 左+右\n",
    "        min_idx, max_idx = 0, 0\n",
    "        min_data, max_data = float(\"inf\"), float(\"-inf\")\n",
    "        for n in range(len(nums)):\n",
    "            if nums[n] > max_data:\n",
    "                max_data, max_idx = nums[n], n\n",
    "            if nums[n] <min_data:\n",
    "                min_data, min_idx = nums[n], n\n",
    "        \n",
    "        if max_idx > min_idx:\n",
    "            # 说明max在左边\n",
    "            ans = min_idx + 1 + len(nums) - max_idx\n",
    "        else:\n",
    "            ans = max_idx + 1 + len(nums) - min_idx    \n",
    "        return min(max(min_idx, max_idx) + 1, \n",
    "        max(len(nums)-max_idx, len(nums)-min_idx),\n",
    "        ans\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimumDeletions(self, nums):\n",
    "        n, i, j = len(nums), nums.index(min(nums)), nums.index(max(nums))\n",
    "        if i > j: i, j = j, i\n",
    "        return min(i + 1 + n - j, j + 1, n - i)         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        min_idx = 0\n",
    "        max_idx = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num < nums[min_idx]:\n",
    "                min_idx = idx\n",
    "            if num > nums[max_idx]:\n",
    "                max_idx = idx\n",
    "        \n",
    "        left = min(min_idx, max_idx)\n",
    "        right = max(min_idx, max_idx)\n",
    "\n",
    "        return min(right+1, n-left, left+1+n-right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx1 = nums.index(max(nums))\n",
    "        idx2 = nums.index(min(nums))\n",
    "        m1 = max(idx1, idx2)+1\n",
    "        m2 = n-min(idx1, idx2)\n",
    "        m3 = n-max(idx1, idx2) + min(idx1, idx2)+1\n",
    "        #print(m1, m2, m3)\n",
    "        return min(m1, m2, m3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        min_idx = -1\n",
    "        max_idx = -1\n",
    "        minnum = float('inf')\n",
    "        maxnum = float('-inf')\n",
    "        for i in range(n):\n",
    "            if(nums[i] > maxnum):\n",
    "                maxnum = nums[i]\n",
    "                max_idx = i \n",
    "            if(nums[i] < minnum):\n",
    "                minnum = nums[i]\n",
    "                min_idx = i\n",
    "        if(min_idx > max_idx):\n",
    "            min_idx, max_idx = max_idx, min_idx\n",
    "        return min(min_idx+1+n-max_idx, max_idx+1, n-min_idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        min_idx = -1\n",
    "        max_idx = -1\n",
    "        minnum = float('inf')\n",
    "        maxnum = float('-inf')\n",
    "        for i in range(n):\n",
    "            if(nums[i] > maxnum):\n",
    "                maxnum = nums[i]\n",
    "                max_idx = i \n",
    "            if(nums[i] < minnum):\n",
    "                minnum = nums[i]\n",
    "                min_idx = i\n",
    "        if(min_idx > max_idx):\n",
    "            min_idx, max_idx = max_idx, min_idx\n",
    "        return min(min_idx+1+n-max_idx, max_idx+1, n-min_idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        \n",
    "        max_ = -inf\n",
    "        min_ = inf\n",
    "        i1 = i2 = -1\n",
    "        for i in range(n):\n",
    "            if nums[i] > max_:\n",
    "                max_ = nums[i]\n",
    "                i1 = i\n",
    "            if nums[i] < min_:\n",
    "                min_ = nums[i]\n",
    "                i2 = i\n",
    "\n",
    "        i1, i2 = min(i1, i2), max(i1, i2)\n",
    "        n1 = (i1 + 1) + (i2 - i1)\n",
    "        n2 = (i1 + 1) + (n - i2)\n",
    "        n3 = (n - i2) + (i2 - i1)\n",
    "        return min(n1, n2, n3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        i = nums.index(max(nums))\n",
    "        j = nums.index(min(nums))\n",
    "        \n",
    "        cmp = []\n",
    "        l = len(nums)\n",
    "\n",
    "        if i < j:\n",
    "            cmp.append(j + 1)\n",
    "            cmp.append(l - i)\n",
    "            cmp.append(l - j + i + 1)\n",
    "            return min(cmp)\n",
    "        \n",
    "        cmp.append(i + 1)\n",
    "        cmp.append(l - j)\n",
    "        cmp.append(l - i + j + 1)\n",
    "        return min(cmp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minIndex = nums.index(min(nums))\n",
    "        maxIndex = nums.index(max(nums))\n",
    "        if minIndex > maxIndex:\n",
    "            minIndex, maxIndex = maxIndex, minIndex\n",
    "        left = minIndex\n",
    "        right = n - 1 - maxIndex\n",
    "        middle = maxIndex - minIndex - 1\n",
    "        #print(left, right, middle)\n",
    "        return n - max(left, right, middle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "       \n",
    "        a=max(nums)\n",
    "        b=min(nums)\n",
    "        c=len(nums)\n",
    "        count=float('inf')\n",
    "        for i in range(4):\n",
    "            if i==0:\n",
    "                count=min(count,max(nums.index(a),nums.index(b))+1)\n",
    "            elif i==1:\n",
    "                count=min(count,max(c-nums.index(a),c-nums.index(b)))\n",
    "            elif i==2:\n",
    "                count=min(count,nums.index(a)+1+(c-nums.index(b)))\n",
    "            elif i==3:\n",
    "                count = min(count, nums.index(b) + 1 + (c - nums.index(a)))\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        minidx = nums.index(min(nums))\n",
    "        maxidx = nums.index(max(nums))\n",
    "        l = min(minidx, maxidx)   # 最值下标中的较小值\n",
    "        r = max(minidx, maxidx)   # 最值下标中的较大值\n",
    "        n = len(nums)\n",
    "        return min(r + 1, n - l, l + 1 + n - r)   # 计算三种情况下删除次数的最小值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        mi = min(nums)\n",
    "        ma = max(nums)\n",
    "        i = next(i for i in range(n) if nums[i] == mi)\n",
    "        j = next(i for i in range(n) if nums[i] == ma)\n",
    "        if i > j:\n",
    "            i, j = j, i\n",
    "        return min(i + 1 + (n - j), j + 1, (n - i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        i = nums.index(min(nums))\n",
    "        a = nums.index(max(nums))\n",
    "        if i<a:\n",
    "            t = min(i+1,len(nums)-a)+a-i\n",
    "            t1 = min(t,i+1+len(nums)-a)\n",
    "            return t1\n",
    "        t = min(a+1,len(nums)-i)+i-a\n",
    "        t1 = min(t,a+1+len(nums)-i)\n",
    "        return t1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        mn, mx = min(nums), max(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == mn:\n",
    "                mn_i = i \n",
    "            if x == mx:\n",
    "                mx_i = i \n",
    "        l = min(mn_i, mx_i)\n",
    "        r = max(mn_i, mx_i)\n",
    "        n = len(nums)\n",
    "        return min(r + 1, n - l, l + 1 + n - r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return n\n",
    "        最小值索引, 最大值索引 = nums.index(min(nums)), nums.index(max(nums))\n",
    "        前, 后 = min(最小值索引, 最大值索引), max(最小值索引, 最大值索引)\n",
    "        return min(后+1, n-前, 前+1+n-后)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        inx1=nums.index(max(nums))\n",
    "        inx2=nums.index(min(nums))\n",
    "        if inx2>inx1:\n",
    "            inx1,inx2=inx2,inx1\n",
    "        return min(inx2+1+n-inx1,inx1+1,n-inx2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        max_i = min_i = -1\n",
    "        max_num, min_num = -inf, inf\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > max_num:\n",
    "                max_i = i\n",
    "                max_num = x\n",
    "            if x < min_num:\n",
    "                min_i = i\n",
    "                min_num = x\n",
    "        if max_i > min_i:\n",
    "            left, right = min_i, max_i\n",
    "        else:\n",
    "            left, right = max_i, min_i\n",
    "        return min(right + 1, n - left, left + 1 + n - right)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        # 简单一次遍历解决问题\n",
    "        i = nums.index(min(nums))\n",
    "        j = nums.index(max(nums))\n",
    "        left = min(i, j)\n",
    "        right = max(i, j)\n",
    "        n = len(nums)\n",
    "        return n - max(left, n-right-1, right-left-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        mx = nums.index(max(nums))\n",
    "        mi = nums.index(min(nums))\n",
    "        if mx < mi: mx, mi = mi, mx\n",
    "        return min(mi + 1 + len(nums) - mx, mx + 1, len(nums) - mi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        minidx = nums.index(min(nums))\n",
    "        maxidx = nums.index(max(nums))\n",
    "        l = min(minidx, maxidx)\n",
    "        r = max(minidx, maxidx)\n",
    "        n = len(nums)\n",
    "        return min(r + 1, n - l, l + 1 + n - r)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        a,b = [inf,-1],[-inf,-1]\n",
    "        n = len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x > b[0]: b = [x,i]\n",
    "            if x < a[0]: a = [x,i]\n",
    "        x,y = a[1],b[1]\n",
    "        if x > y: x,y = y,x\n",
    "        return min(y+1,n-x,x+1+n-y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minimumDeletions(self, nums: List[int]) -> int:\n",
    "    r = {}\n",
    "    l = len(nums)\n",
    "    a, b = nums[0], nums[0]\n",
    "    r[a]=0\n",
    "    for i in range(l):\n",
    "      n = nums[i]\n",
    "      if n < a:\n",
    "        a = n\n",
    "        r[n]= i\n",
    "      if n > b:\n",
    "        b = n\n",
    "        r[n]= i\n",
    "    # print(f\"a{a} b{b} r{r[a]} r{r[b]}\")\n",
    "    pa, pb = r[a], r[b]\n",
    "    # print(f\"p {pa} ~ {pb} l {l}\")\n",
    "    \n",
    "    return min(max(pa, pb) + 1, max(l - pa, l - pb), pa + 1 + l - pb, pb + 1 + l - pa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        mini=nums.index(min(nums))\n",
    "        maxi=nums.index(max(nums))\n",
    "        res1=max(mini+1,maxi+1)\n",
    "        res3=len(nums)-min(mini,maxi)\n",
    "        res2=min(mini+1,maxi+1)+len(nums)-max(mini,maxi)\n",
    "        a=min(res1,res2)\n",
    "        b=min(a,res3)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        max_n = -inf\n",
    "        min_n = inf\n",
    "        for idx,tmp_n in enumerate( nums ):\n",
    "            if tmp_n > max_n:\n",
    "                max_n = tmp_n\n",
    "                max_i = idx\n",
    "            if tmp_n < min_n:\n",
    "                min_n = tmp_n\n",
    "                min_i = idx\n",
    "        type1 = max(min_i , max_i ) + 1\n",
    "        type2 = len(nums) - min( min_i,max_i) \n",
    "        type3 = len(nums) - max(min_i , max_i ) + min( min_i,max_i) + 1\n",
    "        return min(  type1 , type2 , type3 )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        minn = 99999999999\n",
    "        mini = -1\n",
    "        maxn = -99999999999\n",
    "        maxi = -1\n",
    "        for i in range(len(nums)):\n",
    "            if minn > nums[i]:\n",
    "                minn = nums[i]\n",
    "                mini = i\n",
    "            if maxn < nums[i]:\n",
    "                maxn = nums[i]\n",
    "                maxi = i\n",
    "        \n",
    "        # print(minn, mini, maxn, maxi)\n",
    "        l = min(mini, maxi)\n",
    "        r = max(mini, maxi)\n",
    "        # print(l,r)\n",
    "        return min(r+1,len(nums)-l, l+1+len(nums)-r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx1 = nums.index(max(nums))\n",
    "        idx2 = nums.index(min(nums))\n",
    "        if idx1 > idx2:\n",
    "            idx1, idx2 = idx2, idx1\n",
    "        return min(idx2 + 1, n - idx1, idx1+1+n-idx2 ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        minidx = nums.index(min(nums))\n",
    "        maxidx = nums.index(max(nums))\n",
    "        l = min(minidx, maxidx)   # 最值下标中的较小值\n",
    "        r = max(minidx, maxidx)   # 最值下标中的较大值\n",
    "        n = len(nums)\n",
    "        return min(r + 1, n - l, l + 1 + n - r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        min_v = [0, nums[0]]\n",
    "        max_v = [0, nums[0]]\n",
    "        n = len(nums)\n",
    "        for i,num in enumerate(nums):\n",
    "            if num > max_v[1]:\n",
    "                max_v = [i, num]\n",
    "            if num < min_v[1]:\n",
    "                min_v = [i, num]\n",
    "        return int( n - max(n - max(max_v[0], min_v[0]), math.fabs(max_v[0] - min_v[0]), min(max_v[0], min_v[0]) + 1) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        mini=nums.index(min(nums))\n",
    "        maxi=nums.index(max(nums))\n",
    "        res1=max(mini+1,maxi+1)\n",
    "        res3=len(nums)-min(mini,maxi)\n",
    "        res2=min(mini+1,maxi+1)+len(nums)-max(mini,maxi)\n",
    "        a=min(res1,res2)\n",
    "        b=min(a,res3)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        i = nums.index(min(nums))\n",
    "        j = nums.index(max(nums))\n",
    "        l = min(i,j)\n",
    "        r = max(i,j)\n",
    "        return min(r+1,len(nums)-l,l+1+len(nums)-r)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        maxidx = nums.index(max(nums))\n",
    "        minidx = nums.index(min(nums))\n",
    "        l = min(minidx, maxidx)\n",
    "        r = max(minidx, maxidx)\n",
    "        n = len(nums)\n",
    "        return min(r + 1, n - l, l + 1 + n - r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        s = nums.index(min(nums))\n",
    "        b = nums.index(max(nums))\n",
    "        if b < s:\n",
    "            b, s = s, b\n",
    "        l = len(nums)\n",
    "        return min(b + 1, l - s, s + 1 + l - b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <2:\n",
    "            return 1\n",
    "        res = 0\n",
    "        max_index = nums.index(max(nums))\n",
    "        min_index = nums.index(min(nums))\n",
    "        print(max_index,min_index)\n",
    "        if max_index >= n >> 1 and min_index >= n >> 1:\n",
    "            res = n - min(max_index, min_index)\n",
    "        elif max_index <= n >> 1 and min_index <= n >> 1:\n",
    "            res = max(max_index, min_index) + 1\n",
    "        else:\n",
    "            res = min(min(max_index, min_index) + 1 + n - max(max_index, min_index),max(max_index, min_index)+1,n-(min(max_index, min_index) ))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 1\n",
    "        \n",
    "        ma = mi = None\n",
    "        for index, num in enumerate(nums):\n",
    "            if ma is None or ma < num:\n",
    "                p1 = index\n",
    "                ma = num\n",
    "            if mi is None or mi > num:\n",
    "                p2 = index\n",
    "                mi = num\n",
    "        \n",
    "        if p1 > p2:\n",
    "            p1, p2 = p2, p1\n",
    "        \n",
    "        return min(p2 + 1, len(nums) - p1, p1 + 1 + len(nums) - p2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        max_index = nums.index(max(nums))\n",
    "        min_index = nums.index(min(nums))\n",
    "\n",
    "        if max_index == min_index:\n",
    "            if max_index+1 < n-max_index:\n",
    "                res = max_index + 1\n",
    "            else:\n",
    "                res = n-max_index\n",
    "        else:\n",
    "            if max_index < min_index:\n",
    "                if max_index + 1 < n-min_index:\n",
    "                    res = max_index + 1\n",
    "                    n -= res\n",
    "                    min_index -= res\n",
    "                    if min_index + 1 < n-min_index:\n",
    "                        res += min_index +1\n",
    "                    else:\n",
    "                        res += n-min_index\n",
    "                else:\n",
    "                    res = n-min_index\n",
    "                    n -= res\n",
    "                    if max_index + 1 < n - max_index:\n",
    "                        res += max_index +1\n",
    "                    else:\n",
    "                        res += n-max_index\n",
    "            else:\n",
    "                if min_index + 1 < n-max_index:\n",
    "                    res = min_index + 1\n",
    "                    n -=res\n",
    "                    max_index -= res\n",
    "                    if max_index + 1 < n-max_index:\n",
    "                        res += max_index + 1\n",
    "                    else:\n",
    "                        res += n - max_index\n",
    "                else:\n",
    "                    res = n-max_index\n",
    "                    n -= res\n",
    "                    if min_index + 1 < n-min_index:\n",
    "                        res += min_index + 1\n",
    "                    else:\n",
    "                        res += n - min_index\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        mi, mx = min(nums), max(nums)\n",
    "        n = len(nums)\n",
    "        mi_idx, mx_idx = nums.index(mi), nums.index(mx)\n",
    "        if mi_idx > mx_idx:\n",
    "            mi_idx, mx_idx = mx_idx, mi_idx\n",
    "        return min(max(mi_idx, mx_idx) + 1, n - min(mi_idx, mx_idx), mi_idx + n - mx_idx + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        index_max = nums.index(max(nums))\n",
    "        index_min = nums.index(min(nums))\n",
    "        l = min(index_max,index_min)\n",
    "        r = max(index_max,index_min)\n",
    "        return(min(r+1,n-l,l+1+n-r))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        minidx = nums.index(min(nums))\n",
    "        maxidx = nums.index(max(nums))\n",
    "        l = min(minidx, maxidx)  \n",
    "        r = max(minidx, maxidx) \n",
    "        n = len(nums)\n",
    "        return min(r + 1, n - l, l + 1 + n - r) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 2:\n",
    "            return len(nums)\n",
    "\n",
    "        max_ = float('-inf')\n",
    "        max_idx = None\n",
    "\n",
    "        min_ = float('inf')\n",
    "        min_idx = None\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            if n > max_:\n",
    "                max_ = n\n",
    "                max_idx = i\n",
    "            \n",
    "            if n < min_:\n",
    "                min_ = n\n",
    "                min_idx = i \n",
    "\n",
    "        left = min(max_idx, min_idx)\n",
    "        right = max(max_idx, min_idx)\n",
    "\n",
    "        return min(right + 1, len(nums) - left, left + 1 + len(nums) - right)\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return n\n",
    "        最小值索引, 最大值索引 = nums.index(min(nums)), nums.index(max(nums))\n",
    "        return min(max(最小值索引, 最大值索引)+1, n-min(最小值索引, 最大值索引), min(最小值索引, 最大值索引)+1+n-max(最小值索引, 最大值索引))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = nums.index(min(nums))\n",
    "        j = nums.index(max(nums))\n",
    "        if i > j:\n",
    "            i, j = j, i\n",
    "        return min(i + 1 + n - j, n - i, j + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        mx = -inf\n",
    "        mn = inf\n",
    "        id1 = id2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > mx:\n",
    "                id1 = i\n",
    "                mx = num\n",
    "            if num < mn:\n",
    "                id2 = i\n",
    "                mn = num\n",
    "        if id1 > id2:\n",
    "            temp = id2\n",
    "            id2 = id1\n",
    "            id1 = temp\n",
    "        if id1 + 1 < n - id2:\n",
    "            ans = id1 + 1\n",
    "            id1 = id2 - ans\n",
    "        else:\n",
    "            ans = n - id2\n",
    "        \n",
    "        ans += min(id1 + 1, n - ans - id1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        i = nums.index(max(nums))\n",
    "        j = nums.index(min(nums))\n",
    "        \n",
    "        l = len(nums)\n",
    "        maxidx = max(i, j)\n",
    "        minidx = min(i, j)\n",
    "\n",
    "        return min(maxidx + 1, l - minidx, l + minidx - maxidx + 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        mn, mx = min(nums), max(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == mn:\n",
    "                mn_i = i \n",
    "            if x == mx:\n",
    "                mx_i = i \n",
    "        \n",
    "        n = len(nums)\n",
    "        print(n, mn_i, mx_i)\n",
    "        if mx_i <= n // 2 and mn_i <= n // 2:\n",
    "            return max(mn_i, mx_i) + 1\n",
    "        if mx_i >= n // 2 and mn_i >= n // 2:\n",
    "            return max(n - mn_i, n - mx_i)\n",
    "        if mx_i >= n // 2 and mn_i <= n // 2:\n",
    "            return min(n - mn_i, n - mx_i + mn_i + 1, mx_i + 1)\n",
    "        if mx_i <= n // 2 and mn_i >= n // 2:\n",
    "            return min(n - mx_i, n - mn_i + mx_i + 1, mn_i + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<=2:\n",
    "            return n\n",
    "        maxv,minv=max(nums),min(nums)\n",
    "        mxvIndex,mnvIndex=nums.index(maxv),nums.index(minv)\n",
    "        print(mxvIndex,mnvIndex)\n",
    "        leftmove=max(mxvIndex,mnvIndex)+1\n",
    "        rightmove=n-min(mxvIndex,mnvIndex)\n",
    "        twomove=n-max(mxvIndex,mnvIndex)+min(mxvIndex,mnvIndex)+1\n",
    "        return min(leftmove,rightmove,twomove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        max_num=max(nums)\n",
    "        min_num=min(nums)\n",
    "        index_max=nums.index(max_num)\n",
    "        index_min=nums.index(min_num)\n",
    "        #都从前面移除\n",
    "        res1=(max(index_max,index_min)+1)\n",
    "        #都从后面移除\n",
    "        res2=(len(nums)-min(index_max,index_min))\n",
    "        #一个从前面一个从后面\n",
    "        res3=(min(index_max,index_min)+1 +len(nums)-max(index_max,index_min))\n",
    "        return min([res1,res2,res3])\n",
    "        \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        mx = -inf\n",
    "        mn = inf\n",
    "        id1 = id2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > mx:\n",
    "                id1 = i\n",
    "                mx = num\n",
    "            if num < mn:\n",
    "                id2 = i\n",
    "                mn = num\n",
    "        if id1 > id2:\n",
    "            temp = id2\n",
    "            id2 = id1\n",
    "            id1 = temp\n",
    "        if id1 + 1 < n - id2:\n",
    "            ans = id1 + 1\n",
    "            id1 = id2 - ans\n",
    "        else:\n",
    "            ans = n - id2\n",
    "        \n",
    "        ans += min(id1 + 1, n - ans - id1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        mx = -inf\n",
    "        mn = inf\n",
    "        id1 = id2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > mx:\n",
    "                id1 = i\n",
    "                mx = num\n",
    "            if num < mn:\n",
    "                id2 = i\n",
    "                mn = num\n",
    "        if id1 > id2:\n",
    "            temp = id2\n",
    "            id2 = id1\n",
    "            id1 = temp\n",
    "        print(mx, mn, id1, id2)\n",
    "        if id1 + 1 < n - id2:\n",
    "            ans = id1 + 1\n",
    "            id1 = id2 - ans\n",
    "        else:\n",
    "            ans = n - id2\n",
    "        \n",
    "        ans += min(id1 + 1, n - ans - id1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDeletions(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        mx = -inf\n",
    "        mn = inf\n",
    "        id1 = id2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > mx:\n",
    "                id1 = i\n",
    "                mx = num\n",
    "            if num < mn:\n",
    "                id2 = i\n",
    "                mn = num\n",
    "        if id1 > id2:\n",
    "            temp = id2\n",
    "            id2 = id1\n",
    "            id1 = temp\n",
    "        print(mx, mn, id1, id2)\n",
    "        if id1 + 1 < n - id2:\n",
    "            ans = id1 + 1\n",
    "            id1 = id2 - ans\n",
    "        else:\n",
    "            ans = n - id2\n",
    "        \n",
    "        ans += min(id1 + 1, n - ans - id1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
